#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 227. 基本计算器 II.py
@time: 2022/3/4 13:50
@desc: https://leetcode-cn.com/problems/basic-calculator-ii/
> 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

示例 1：
    输入：s = "3+2*2"
    输出：7

1. 栈
2.
    Ot(N)，遍历字符串一次；
    Os(N)，遍历字符串一次
'''
class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        stack = []
        sign = '+'
        num = 0
        for i in range(n):
            if '0'<=s[i]<='9':
                num = num*10+int(s[i])
            # i==n-1时，需要做最后的计算
            if i==n-1 or s[i] in '+-*/':
                if sign == '+':
                    stack.append(num)
                elif sign=='-':
                    stack.append(-num)
                elif sign=='*':
                    stack.append(stack.pop()*num)
                else:
                    stack.append(stack.pop()//num)
                sign = s[i]
                num = 0
        return sum(stack)

